#include <iostream>
#include <cstdio>
using namespace std;

int n, m, D;
int c[100][100], a[100][100], dp[100][101];
int usd, was[100][101], inf;

void load()
{
	scanf("%d%d%d", &D, &n, &m);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &c[i][j]);
    inf = D + 1;
    //for (int i = 0; i < m; i++)
      //  for (int j = 0; j <= n; j++)
        //    dp[i][j] = -1;
}

int f(int i, int j)
{
    if (j == n) return 0;
    if (was[i][j] == usd) return dp[i][j];
    was[i][j] = usd;
    dp[i][j] = inf;
    for (int k = 0; k < m; k++)
    {
        dp[i][j] = min(dp[i][j], f(k, j + 1) + a[k][j] + c[i][k]);
    }
    return dp[i][j];
}

void solve()
{
	usd++;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < m; k++)
                c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
    int res = inf;
    for (int i = 0; i < m; i++)
        res = min(res, f(i, 0));
    printf("%d\n", D - res);
}

int main()
{
//	freopen("gift.in", "rt", stdin);
//	freopen("gift.out", "wt", stdout);

	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		load();
		solve();
	}
	return 0;
}